#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <sys/types.h>

#define ARRAY_SIZE (1 << 30)                                    // test array size is 2^28

typedef unsigned char BYTE;										// define BYTE as one-byte type

BYTE array[ARRAY_SIZE];											// test array
const int L2_cache_size = 1 << 18;

#define VISITTIMESLOG 27 // 访问次数的对数

#define KBLOG (10) // ..K 的log
#define MBLOG (20) // ..M 的log
#define KB (1024)

#define L1CACHESZIE (1 << 15) // 任务一测量得到


double get_usec(const struct timeval tp0, const struct timeval tp1)
{
    return 1000000 * (tp1.tv_sec - tp0.tv_sec) + tp1.tv_usec - tp0.tv_usec;
}

// have an access to arrays with L2 Data Cache'size to clear the L1 cache
void Clear_L1_Cache()
{
	memset(array, 0, L2_cache_size);
}

// have an access to arrays with ARRAY_SIZE to clear the L2 cache
void Clear_L2_Cache()
{
	memset(array, 0, ARRAY_SIZE);
}

void Test_Cache_Size()
{
	printf("**************************************************************\n");
	printf("Cache Size Test\n");

	struct timeval tp[2]; // 计时数组

	int arraysizelog = 0; // 定义数组大小的对数
	unsigned long long arraysize = 0; // 定义数组大小
	unsigned long long visittimes = 0; // 测试时的访存次数
	double averagetime = 0; // 平均访问时间 us

	unsigned long long i = 0; // for 循环

	// 2KB - 2MB
	for(arraysizelog = 1 + KBLOG; arraysizelog <= 1 + MBLOG; arraysizelog++){
		arraysize = (1 << arraysizelog);
		visittimes = (1 << VISITTIMESLOG);

		// clear
		Clear_L2_Cache();

		// 循环访存array[0 ~ (arraysize -1)]共visittimes次 
		gettimeofday(&tp[0], NULL);
		for(i=0; i < visittimes; i++)
				array[rand() % arraysize] = i;
		gettimeofday(&tp[1], NULL);

		averagetime = get_usec(tp[0], tp[1]) / visittimes;
		printf("[Test_Array_Size = %4lldKB] \t Average access time: %.7fus\n", arraysize / KB, averagetime);
	}
}

void Test_L1C_Block_Size()
{
	printf("**************************************************************\n");
	printf("L1 DCache Block Size Test\n");

	struct timeval tp[2];

	int steplen = 0; // 步长
	unsigned long long offset = 0; // 第一个访问的数据
	unsigned long long visittimes = 0; // 访问次数
	unsigned long long i = 0; // for 循环

	double averagetime = 0;
	
	for(steplen=16; steplen<1024; steplen <<= 1 ){
		// 清空L1
		Clear_L1_Cache();

		// 每轮都是新数组
		BYTE * testarray = (BYTE *)malloc(ARRAY_SIZE);

		visittimes = 1 << VISITTIMESLOG;

		gettimeofday(&tp[0], NULL);
		for(i=0; i<visittimes; i++){
			testarray[offset] = i;
			offset = (offset + steplen) % ARRAY_SIZE;
		}
		gettimeofday(&tp[1], NULL);

		averagetime = get_usec(tp[0], tp[1]) / visittimes;
		free(testarray); // 使用完释放

		printf("[Test_Array_Jump = %3dB] \t Average access time: %.7fus\n", steplen, averagetime);
		
	}	
}

void Test_L2C_Block_Size()
{
	printf("**************************************************************\n");
	printf("L2 Cache Block Size Test\n");
	
	Clear_L2_Cache();											// Clear L2 Cache
	
	// TODO
}

void Test_L1C_Way_Count()
{
	printf("**************************************************************\n");
	printf("L1 DCache Way Count Test\n");

	struct timeval tp[2];

	unsigned long long arraysize = 2 * L1CACHESZIE; //测试数组的大小


	double averagetime = 0;

	unsigned long long arrayblocksize = 0; // 测试数组分组后每组的大小
	int arraygroupsnum = 0; // 测试数组化分为分为多少组
	unsigned long long visittimes = 0; // 访问次数
	unsigned long long cycles = 0; // 重复访问所有的奇数块多少圈
	int i = 0; // for 循环
	unsigned long long j = 0;
	unsigned long long k = 0;
	unsigned long long count = 0;
	for(arraygroupsnum=4; arraygroupsnum<=128; arraygroupsnum *= 2){
		count = 0;
		BYTE * testarray = (BYTE *)malloc(arraysize); // 测试数组


		Clear_L1_Cache();

		arrayblocksize = arraysize / arraygroupsnum; // 数组每一个块的大小
		visittimes = 1 << VISITTIMESLOG;
		cycles = visittimes / L1CACHESZIE;

		gettimeofday(&tp[0], NULL);
		for(k = 0;k<cycles;k++){
			for(i = 0; i<arraygroupsnum; i++){
				// 遍历全部奇数块，奇数块范围：i*arrayblocksize ~ (i+1)arrayblocksize i为奇数
				if((i%2)!=0)
					for(j = i*arrayblocksize; j<(i+1)*arrayblocksize; j++)
						testarray[j] = k;
			}
		}
		gettimeofday(&tp[1], NULL);

		averagetime = get_usec(tp[0], tp[1]) / visittimes;

		free(testarray);
		printf("[Test_Split_Groups = %3d] \t Average access time: %.7fus\n", arraygroupsnum, averagetime);
	}

}

void Test_L2C_Way_Count()
{
	printf("**************************************************************\n");
	printf("L2 Cache Way Count Test\n");
	
	// TODO
}

void Test_Cache_Write_Policy()
{
	printf("**************************************************************\n");
	printf("Cache Write Policy Test\n");

	// TODO
}

void Test_Cache_Swap_Method()
{
	printf("**************************************************************\n");
	printf("Cache Replace Method Test\n");

	// TODO
}

void Test_TLB_Size()
{
	printf("**************************************************************\n");
	printf("TLB Size Test\n");

	const int page_size = 1 << 12;								// Execute "getconf PAGE_SIZE" under linux terminal
	struct timeval tp[2];
	double averagetime = 0;
	unsigned long long visittimes = 0; // 访问次数
	int pagesnum = 0; // 访问页的个数
	
	int i = 0; // for循环
	unsigned long long j = 0; // for循环

	for(pagesnum=16; pagesnum<=512; pagesnum *= 2){
		BYTE* testarray = (BYTE*)malloc(ARRAY_SIZE); // 测试数组

		visittimes = 1 << VISITTIMESLOG; // 访问次数

		// 消除cache的影响
		Clear_L2_Cache(); // 1. Clear L1 and L2
		for(i=0; i<pagesnum; i++)
			testarray[i * page_size] = i; // 2. Add to TLB
										  // 3. and Add to L1 L2 Cache

		gettimeofday(&tp[0], NULL);
		for(j = 0;j < visittimes; j++)
			testarray[(j % pagesnum) * page_size] = j; // 访问某一页
		gettimeofday(&tp[1], NULL);
			
		averagetime = get_usec(tp[0], tp[1]) / visittimes;

		free(testarray);

		printf("[Test_TLB_Entries = %4d] \t Average access time: %.7fus\n", pagesnum, averagetime);
	}

    // TODO
}

int main()
{
	Test_Cache_Size(); 
	Test_L1C_Block_Size();
	// Test_L2C_Block_Size();
	Test_L1C_Way_Count();
	// Test_L2C_Way_Count();
	// Test_Cache_Write_Policy();
	// Test_Cache_Swap_Method();
	Test_TLB_Size();
	
	return 0;
}
